package cn.cxq.learning.search;

/**
 * 二分查找
 */
public class BinarySearch {

    public static int recurSearch(int[] arr, int value) {

        int left = 0;
        int right = arr.length - 1;

        return itemSearch(arr, value, left, right);
    }

    private static int itemSearch(int[] arr, int value, int left, int right) {
//        int mid = (left + right) / 2;
//
//        if (value == arr[mid]) return mid;
//        else if (value > arr[mid]) {
//            if (mid + 1 > right) return -1;
//            return itemSearch(arr, value, mid + 1, right);
//        } else {
//            if (left > mid - 1) return -1;
//            return itemSearch(arr, value, left, mid - 1);
//        }
        if (left > right) {
            return -1;
        }

        int middle = (left + right) / 2;

        if (value == arr[middle]) return middle;
        else if (value > arr[middle]) return itemSearch(arr, value, middle + 1, right);
        else return itemSearch(arr, value, left, middle - 1);
    }

    public static int search(int[] arr, int value) {

        int left = 0;
        int right = arr.length - 1;


        while (left <= right) {

            int mid = (left + right) / 2;

            if (value == arr[mid]) return mid;
            else if (value > arr[mid]) left = mid + 1;
            else right = mid - 1;
        }

        return -1;
    }
}
